package reg_alloc;

/********************************
 * Authors: Gustavo Solaira and Rafael Dominiquini
 * MC011 - Liveness Analysis
 ********************************/

import java.io.PrintStream;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;

import temp.Temp;
import util.List;
import flow_graph.FlowGraph;
import graph.Node;

public class Liveness extends InterferenceGraph
{
    private FlowGraph graph;
    private List<Node> revNodes;
    
    public void addEdge(Node src, Node dst)
    {
        if ( src != dst && !dst.comesFrom(src) && !src.comesFrom(dst))
            super.addEdge(src, dst);
    }
    
    // estruturas usadas para computar a DFA
    private Hashtable<Node, HashSet<Temp>> in;
    private Hashtable<Node, HashSet<Temp>> out;
    private Hashtable<Node, HashSet<Temp>> gen;
    private Hashtable<Node, HashSet<Temp>> kill;
        
    public void show(PrintStream o)
    {       
        for ( List<Node> aux = this.nodes(); aux != null; aux = aux.tail )
        {
            Temp t = revMap.get(aux.head);
            
            o.print(t + ": [ ");
            for ( List<Node> adjs = aux.head.adj(); adjs != null; adjs = adjs.tail )
                o.print( revMap.get(adjs.head) + " ");
            //o.println("]");
        }
    }
    
    // coisas uteis
    private MoveList moveList = null;
    
    private Hashtable<Node, Temp> revMap = new Hashtable<Node, Temp>();
    private Hashtable<Temp, Node> map = new Hashtable<Temp, Node>();
    
    public Liveness(FlowGraph g)
    {
        super();
    
        graph = g;
        
        if (graph == null)
        {
        	return;
        }
        
        /* cria lista de nós reversa para acelerar liveness */
        revNodes = reverseList(graph.nodes());
                    
        computeGenKill();
        computeDFA();
        buildInterference();
    }
    
    /* reverse MiniJava list using Java list */
    private List<Node> reverseList(List<Node> orig)
    {
    	java.util.LinkedList<Node> aux = new java.util.LinkedList<Node>();
    	List<Node> auxRes = new List<Node>(null, null);
    
    	for(List<Node> iter = orig; iter != null; iter = iter.tail)
        {
    		aux.add(iter.head);
        }
    	
    	Collections.reverse(aux);
    	List<Node> iterRes = auxRes;
    	
    	for(Node n : aux)
    	{
    		iterRes.head = n;
    		iterRes.tail = new List<Node>(null, null);
    		iterRes = iterRes.tail;
    	}
    	
    	iterRes = auxRes;
    	
    	while (iterRes != null)
    	{
    		if (iterRes.tail.head == null)
    		{
    			iterRes.tail = null;
    		}
    		
    		iterRes = iterRes.tail;
    	}
    	
    	return auxRes;
    }

    public void dump(PrintStream outStream)
    {
        int c=0;
        for(List<Node> aux = graph.nodes(); aux != null; aux = aux.tail, c++)
        {
            HashSet<Temp> i = in.get(aux.head);
            HashSet<Temp> o = out.get(aux.head);
            HashSet<Temp> g = gen.get(aux.head);
            HashSet<Temp> k = kill.get(aux.head);
            
            outStream.println(c+": gen:"+g+" kill:"+k+" in:"+i+" out:"+o);
        }
    }
    
    private void computeGenKill()
    {
        kill = new Hashtable<Node, HashSet<Temp>>();
        gen  = new Hashtable<Node, HashSet<Temp>>();
        
        for(List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail)
        {
            HashSet<Temp> k = new HashSet<Temp>();
            HashSet<Temp> g = new HashSet<Temp>();
            
            // kill
            for ( List<Temp> aux = graph.def(nodes.head); aux != null; aux = aux.tail )
                k.add(aux.head);
            
            // gen
            for ( List<Temp> aux = graph.use(nodes.head); aux != null; aux = aux.tail )
                g.add(aux.head);
            
            kill.put(nodes.head, k);
            gen.put(nodes.head, g);
        }
    }
    
    /* Compute the in and out of each node
     * in[n] = gen[n] U (out[n] - kill[n])
     * out[n] = Us=succ[n] in[s]
     */
    private void computeDFA()
    {	
    	in = new Hashtable<Node, HashSet<Temp>>();
    	out = new Hashtable<Node, HashSet<Temp>>();

    	/* Used to check if the set has been changed */
    	HashSet<Temp> in_prime = new HashSet<Temp>();
    	HashSet<Temp> out_prime = new HashSet<Temp>();
		
		/* Only need to do add the gen temps once */
    	/* in[n] = ***gen[n]*** U (out[n] - kill[n]) */
		for (List<Node> p = revNodes; p != null; p = p.tail)
		{
			Node n = p.head;
			
			/* Create the temp hashsets */
			in.put(n, new HashSet<Temp>());
			out.put(n, new HashSet<Temp>());
			
			/* Add gen nodes */
			in.get(n).addAll(gen.get(n));
		}
		
		boolean stop;
    	
		/* Fixed point iteration */
    	do {
    		stop = true;
    		
    		for (List<Node> p = revNodes; p != null; p = p.tail)
    		{
        		in_prime.clear();
        		out_prime.clear();
        		
    			Node n = p.head;
    			
    			in_prime.addAll(in.get(n));
    			out_prime.addAll(out.get(n));
    			
    			/* in[n] = gen[n] U ***(out[n] - kill[n])*** */
    			HashSet<Temp> aux_set = new HashSet<Temp>();
    			aux_set.addAll(out.get(n));
    			aux_set.removeAll(kill.get(n));
    			
    			in.get(n).addAll(aux_set);
    			   			
    			/*  out[n] = Us=succ[n] in[s] */
    			/* Do for all successors */
    			for (List<Node> aux_succ = n.succ(); aux_succ != null; aux_succ = aux_succ.tail)
    			{
    				out.get(n).addAll(in.get(aux_succ.head));
    			}
    			
    			/* If lists are equal than do not continue */
    			if ((! in_prime.containsAll(in.get(n))) || (! out_prime.containsAll(out.get(n))))
    				stop = false;
    		}
    		
    	/* Verify if in and out have changed */
    	} while (! stop);
    }

	private Node getNode(Temp t)
    {
        Node n = map.get(t);
        
        if ( n == null )
        {
            n = this.newNode();
            
            map.put(t, n);
            revMap.put(n, t);
        }
        
        return n;
    }
    
    private void handle(Node instr)
    {
        for( List<Temp> defs = graph.def(instr); defs != null; defs = defs.tail )
        {
            Node currentTemp = this.getNode(defs.head);
            
            for( Temp liveOut : out.get(instr) )
            {                
                Node currentLiveOut = this.getNode(liveOut);
                this.addEdge(currentTemp, currentLiveOut);
            }
        }
    }
    
    private void handleMove(Node instr)
    {
        Node dst = this.getNode(graph.def(instr).head);
        Node src = this.getNode(graph.use(instr).head);
        
        moveList = new MoveList(src, dst, moveList);
        
        for( Temp t : out.get(instr) )
        {
            Node currentOut = this.getNode(t);
            
            if ( currentOut != src )
            {
                //this.addEdge(currentOut, dst);
                this.addEdge(dst, currentOut);
            }
        }
    }
    
    private void buildInterference()
    {
        // Estamos sentados sobre ombros de um gigante...
        // Aqui, nos temos uma lista sobre todos os temporarios
        // vivos no fim de cada no. Desta forma, eh relativamente
        // facil construir a lista de adjacencia.
        
        for ( List<Node> instrs = graph.nodes(); instrs != null; instrs = instrs.tail )
        {
            Node current = instrs.head;
            
            if ( graph.isMove(current))
                handleMove(current);
            else
                handle(current);
        }
    }
    
    public Node tnode(Temp temp)
    {
        Node n = map.get(temp);
        
        if ( n == null )
        {
            map.put(temp, n = newNode() );
            revMap.put(n, temp);
        }
        
        return n;
    }

    public Temp gtemp(Node node)
    {
        return revMap.get(node);
    }

    public MoveList moves()
    {
        return moveList;
    }

    public HashSet<Temp> Out(Node node)
    {
        return out.get(node);
    }    
}
